
<!DOCTYPE html>
<!--[if IEMobile 7 ]><html class="no-js iem7"><![endif]-->
<!--[if lt IE 9]><html class="no-js lte-ie8"><![endif]-->
<!--[if (gt IE 8)|(gt IEMobile 7)|!(IEMobile)|!(IE)]><!--><html class="no-js" lang="en"><!--<![endif]-->
<head>
  <meta charset="utf-8">
  <title>深入解析Bloom Filter(中) - Yebangyu's Blog</title>
  <meta name="author" content="Yebangyu">

  
  <meta name="description" content="本文介绍d-left hashing和d-left counting bloom filter">
  <meta name="keywords" content="d-left hashing d-left counting bloom filter">

  <!-- http://t.co/dKP3o1e -->
  <meta name="HandheldFriendly" content="True">
  <meta name="MobileOptimized" content="320">
  <meta name="viewport" content="width=device-width, initial-scale=1">

  
  <link rel="canonical" href="http://www.yebangyu.org/blog/2016/01/29/insidethebloomfilter/">
  <link href="/favicon.png" rel="icon">
  <link href="/stylesheets/screen.css" media="screen, projection" rel="stylesheet" type="text/css">
  <link href="/atom.xml" rel="alternate" title="Yebangyu's Blog" type="application/atom+xml">
  <script src="/javascripts/modernizr-2.0.js"></script>
  <script src="//ajax.lug.ustc.edu.cn/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
  <script>!window.jQuery && document.write(unescape('%3Cscript src="/javascripts/libs/jquery.min.js"%3E%3C/script%3E'))</script>
  <script src="/javascripts/octopress.js" type="text/javascript"></script>
  <!--Fonts from Google"s Web font directory at http://google.com/webfonts -->
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Serif:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Sans:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>

  

</head>

<body   >
  <header role="banner"><hgroup>
  <h1><a href="/">Yebangyu's Blog</a></h1>
  
    <h2>Fond of Concurrency Programming and Machine Learning</h2>
  
</hgroup>

</header>
  <nav role="navigation"><ul class="subscription" data-subscription="rss">
  <li><a href="/atom.xml" rel="subscribe-rss" title="subscribe via RSS">RSS</a></li>
  
</ul>
  
<form action="https://www.google.com/search" method="get">
  <fieldset role="search">
    <input type="hidden" name="sitesearch" value="www.yebangyu.org">
    <input class="search" type="text" name="q" results="0" placeholder="Search"/>
  </fieldset>
</form>
  
<ul class="main-navigation">
  <li><a href="/">Blog</a></li>
  <li><a href="/blog/archives">Archives</a></li>
  <li><a href="/about">About Me</a></li>
</ul>

</nav>
  <div id="main">
    <div id="content">
      <div>
<article class="hentry" role="article">
  
  <header>
    
      <h1 class="entry-title">深入解析Bloom Filter(中)</h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-01-29T22:38:31+08:00'><span class='date'><span class='date-month'>Jan</span> <span class='date-day'>29</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>10:38 pm</span></time>
        
      </p>
    
  </header>


<div class="entry-content"><p>本篇将介绍：</p>

<blockquote>
  <ul>
    <li>d-left hashing</li>
    <li>d-left counting bloom filter</li>
  </ul>
</blockquote>

<p>在<a href="http://www.yebangyu.org/blog/2016/01/23/insidethebloomfilter/">上篇</a>文章，我们介绍了Standard Bloom Filter(SBF)和Counting Bloom Filter(CBF)。简单回顾下，我们大概思路和历程是：为了解决允许false positive下的membership问题，我们设计了哈希表算法，由于它所需空间巨大，我们引入bitmap方法；因为它false positive possibility太大，我们引入了SBF，它使用多个独立的、均匀分布的哈希函数。而SBF的一个缺点是不支持删除操作，为了能够删除，我们引入了CBF，然而，CBF存在一个问题。</p>

<p>什么问题呢？那就是空间利用率不高。这可以通过简单的数学计算知道大概：</p>

<p>考察某个位置，该位置的计数器counter的值$\xi$</p>

<p>$P(\xi = c) \approx \binom{mk}{c} {(\frac{1}{n})}^{c}({1-\frac{1}{n}})^{mk-c} = B(km,\frac{1}{n})$</p>

<!--more-->

<p>若二项分布B(n,p)里n很大，p很小时，二项分布的极限近似分布是泊松分布$P(\lambda=k) = \frac{\lambda^k}{k!}{e}^{-\lambda}$，其中$\lambda=np=\frac{km}{n}$，并结合$k = \frac{n}{m}ln2$，可以得到，counter的期望值为：</p>

<p>$E(\xi) = \lambda = np = ln2 \approx 0.7$</p>

<p>即大量的counter的值都是0，空间效率不高。</p>

<p>在介绍新的Bloom Filter之前，我们一起先看看什么是所谓的d-left hashing。</p>

<h3 id="d-left-hashing">d-left hashing</h3>

<p>在d-left hashing中，我们有d张哈希子表（序号分别为1,2,…d，并且假设是从左到右），每张子表都包含B个bucket，每个bucket都包含w个cell，每个cell可以存放一个元素。</p>

<p>为了插入一个元素x，我们：</p>

<p>1，首先通过一个哈希函数hf，得到x的哈希函数值value = hf(x)</p>

<p>2，通过value，得到d个位置（每个位置对应每张子表），表示为：</p>

<p>(1,$B_1$) , (2,$B_2$),… (d,$B_d$)</p>

<p>其中(i,$B_i$)表示第i张子表，Bucket的index为$B_i$。</p>

<p>那么，到底插入哪张表呢？d-left hashing选择$B_i$中负载最小（已经存放的元素最少）的位置。注意，这里说的是bucket的负载，不是子表的负载。如果有多个子表对应的位置负载都是最小，那么选择最左边（序号最小）的子表插入。</p>

<p>为了查找该元素，我们需要检查d个位置，wd个cell（元素）。</p>

<h3 id="d-left-counting-bloom-filter">d-left counting bloom filter</h3>

<p>在基于d-left hashing的CBF中，我们有d张哈希子表（序号分别为1,2,…d，并且假设是从左到右），每张子表都包含B个bucket，每个bucket都包含w个cell，每个cell可以存放一个counter和一个fingerprint。</p>

<p>为了插入一个元素x，我们：</p>

<p>1，首先通过一个哈希函数hf，得到x的哈希函数值value = hf(x)</p>

<p>2，通过value，得到d个位置（每个位置对应每张子表）和对应的fingerprint，表示为d个位置向量：</p>

<p>(1,$B_1$,$fp_1$) , (2,$B_2$,$fp_2$),… (d,$B_d$,$fp_d$)</p>

<p>其中位置向量(i,$B_i$,$fp_i$)表示第i张子表，Bucket的index为$B_i$，fingerprint为$fp_i$。</p>

<p>3，通过d-left hashing将x插入，如果插入的位置(i,$B_i$,$fp_i$)上已经有cell的fingerprint等于$fp_i$，那么只需要将它的counter++即可。</p>

<p>举个栗子，假设某时刻，我们有：</p>

<p><img src="http://7xnljs.com1.z0.glb.clouddn.com/dleftcbf1.jpg" alt="d-leftcbf1" /></p>

<p>2张子表（d=2），每张子表有6个bucket（B=6），每个bucket包括3个cell（w=3），每个cell可以存放一个counter(4位表示，最大值为16)和fingerprint（6位表示）。</p>

<p>假如我们要插入元素x，我们对它进行hash，得到两个位置向量：</p>

<p>(1, 1, 010100)和(2, 2, 010101)</p>

<p>$d_1$子表中index为1的bucket的负载，要小于$d_2$子表中index为2的bucket的负载，因此，我们选择插入$d_1$中，如下：</p>

<p><img src="http://7xnljs.com1.z0.glb.clouddn.com/dleftcbf2.jpg" alt="d-leftcbf2" /></p>

<p>如果得到的位置向量分别是(1, 1, 001100)和(2, 2, 010101)呢？那么，还是插入到$d_1$中index为1的bucket中，但是只需要将第二个cell里的counter++即可，如下图：</p>

<p><img src="http://7xnljs.com1.z0.glb.clouddn.com/dleftcbf3.jpg" alt="d-leftcbf3" /></p>

<p>看起来很完美，但是这种方案在删除时会有问题。比如说，还是刚才的例子，我们欲插入x和y。分别得到x和y的位置向量们：</p>

<p>x: (1, 1, 010100)和(2, 2, 010100)</p>

<p>y: (1, 1, 010100)和(2, 4, 010100)</p>

<p>根据d-left hashing，x被插入到$d_1$中index为1的bucket中；y被插入到$d_2$中index为4的bucket中。好，这没问题。如果现在要删除y呢？我们需要检查两个位置，$d_1$中的index为1的bucket，以及$d_2$中index为4的bucket，要删哪个？fp都是010100啊。这就出现问题。</p>

<p>什么时候会出现这种问题？当以下条件满足时：</p>

<p>1，两个元素的有公共【重合】的位置向量。位置向量相同，表示同一个子表，同一个bucket，以及相同的fingerprint。</p>

<p>2，其中一个元素被插入了公共位置向量对应的位置，另外一个元素没有。</p>

<p>3，欲删除未使用公共位置向量的元素（比如说上例中的y）</p>

<p>为了解决这个问题，作者做了两点改进：</p>

<p>I 引入d轮随机置换。</p>

<p>置换，即一一映射。假设置换为P，输入为a和b，那么将满足：</p>

<p>如果$a = b$，那么$P(a) = P(b)$</p>

<p>如果$a \neq b$ ，那么 $P(a) \neq P(b)$</p>

<p>为了插入x，我们首先通过一个哈希函数hf，计算它的哈希函数值value = hf(x)。然后，我们对value进行d轮随机置换，得到d个位置向量：</p>

<p>$P_1(value) = (1, B_1, fp_1)$</p>

<p>$P_2(value) = (2, B_2, fp_2)$</p>

<p>……</p>

<p>$P_d(value) = (d, B_d, fp_d)$</p>

<p>这里面有一个小问题：如果要插入的元素x和y不等，那么它们的置换可能相等吗？当然可能。因为x和y虽然不等，但是它们的hash value可能相等，这样它们的置换结果即位置向量可能相同。</p>

<p>别忘了，我们是对x和y的hash value进行置换，不是对x和y进行置换。</p>

<p>网上流传很广的<a href="http://blog.csdn.net/jiaomeng/article/details/1526099">这篇</a>文章的解释是错误的，小心！！！</p>

<p>II 插入修正</p>

<p>当得到d个位置向量后，和上面介绍的过程稍微不同：我们首先需要根据d个位置向量，从第1个子表开始，对每个子表$d_i$，去对应的位置$B_i$处查找是否有cell中的fp等于$fp_i$，如果有，我们把相应的counter++，插入动作完成，不用再继续检查后续子表了。</p>

<p>否则，当所有d个子表都没有对应的$fp_i$时，我们运用d-left hashing，插入x。</p>

<p>综合运用这两点，我们知道上面所说的删除时的问题已经不存在了。</p>

<p>假如欲插入x和y，分别对它们的hash value进行d轮（这里d=2）随机置换后，有没有可能得到如下的位置向量？</p>

<p>x: (1, 1, 010100)和(2, 2, 010101)</p>

<p>y: (1, 1, 010100)和(2, 4, 010111)</p>

<p>不可能。</p>

<p>注意到，x和y的第一个位置向量（对应第一张子表）完全相同（bucket index相同，fp也相同），也就是</p>

<p>$P_1(hf(x)) = P_1(hf(y))$</p>

<p>那么可以推出hf(x) = hf(y)，也就是x和y的哈希函数值相等，那么对于任何的i都有$P_i(hf(x)) = P_i(hf(y))$。</p>

<p>因此：</p>

<p>如果$hf(x) = hf(y)$，那么$P_i(hf(x)) = P_i(hf(y))$ (i=1,2,3…d)，假如先插入x后插入y，插入y的时候，会更新counter。后续删除x或者y都不存在上述问题。</p>

<p>如果$hf(x) \neq hf(y)$，那么$P_i(hf(x)) \neq P_i(hf(y))$ (i=1,2,3…d)，那么x和y没有公共的位置向量。后续删除x或者y都不存在上述问题。</p>

<h2 id="section">附录</h2>

<h3 id="section-1">如何随机置换</h3>

<p>作者提供了一个简单的函数：</p>

<p>$P_i(value) = (a * value ) mod 2^B$</p>

<p>其中value的范围是[0, $2^B$]，a是随机的一个奇数。</p>

<h3 id="section-2">数学分析</h3>

<p>首先，如果z是false positive，那么它的哈希函数值会和集合S中的某个元素的哈希函数值相等。也就是</p>

<p>hf(z) = hf(e) 其中 $e\in S$</p>

<p>这是因为，如果z是false positive，那么</p>

<p>$p_i(hf(z)) = p_i(hf(e))$</p>

<p>根据置换的性质，可得hf(z) = hf(e)</p>

<p>因此，false positive possibility为</p>

<p>$P = 1 - (1 - \frac{1}{B}*\frac{1}{2^r})^m$</p>

<p>根据伯努利公式，当x很小时，$(1+x)^a \approx 1 + ax$，所以</p>

<p>$P \approx 1 - (1 - m * \frac{1}{B} * \frac{1}{2^r}) \approx \frac{m}{B*2^r}$</p>

<p>那么d-left CBF的false positive和空间利用情况如何？我们下面简单分析一下：</p>

<p>比较嘛，肯定是相同的空间利用，比较谁的false positive possibility小；相同的false positive possibility下，谁所需空间少。</p>

<p>在CBF中，假设counter需要c位（<a href="http://www.yebangyu.org/blog/2016/01/23/insidethebloomfilter/">上次</a>我们分析过，c取4足矣），那么所需的空间是cn。结合$k = \frac{n}{m}ln2$，false positive possibility大约为$(0.6185)^{\frac{n}{m}}$。</p>

<p>在d-left CBF中，我们选择d=4，B=$\frac{m}{24}$，w=8（平均负载为6，这样$4 * \frac{m}{24} * 6 = m$），counter占用2位，fingerprint占用r位。那么它的空间占用为</p>

<p>$4 * \frac{m}{24} * 8  * (2+r) = \frac{4m(r+2)}{3}$</p>

<p>而false positive possibility的大概为 $\frac{m}{B*2^r} = 24 * \frac{1}{2^r}$ (别忘了，B=$\frac{m}{24}$ )</p>

<p>通过计算不难发现，当空间占用相等时，d-left CBF的false positive possibility是CBF的百分之一；当false positive possibility相等时，d-left CBF所需空间是CBF的一半。</p>

<h2 id="section-3">感谢</h2>

<p>特别感谢<a href="http://www.xiaolili.net/">汪立</a>大神参与讨论。</p>
</div>


  <footer>
    <p class="meta">
      
  

<span class="byline author vcard">Posted by <span class="fn">Yebangyu</span></span>

      




<time class='entry-date' datetime='2016-01-29T22:38:31+08:00'><span class='date'><span class='date-month'>Jan</span> <span class='date-day'>29</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>10:38 pm</span></time>
      

<span class="categories">
  
    <a class='category' href='/blog/categories/suan-fa/'>算法</a>
  
</span>


    </p>
    
      <div class="sharing">
  
  
  
</div>

    
    <p class="meta">
      
        <a class="basic-alignment left" href="/blog/2016/01/24/spinlock-and-mutex/" title="Previous Post: Spinlock and mutex">&laquo; Spinlock and mutex</a>
      
      
        <a class="basic-alignment right" href="/blog/2016/02/01/detectmemoryghostinmultithread/" title="Next Post: 多线程内存问题分析之mprotect方法">多线程内存问题分析之mprotect方法 &raquo;</a>
      
    </p>
  </footer>
</article>


</div>

<aside class="sidebar">
  
    <section>
  <h1>Recent Posts</h1>
  <ul id="recent_posts">
    
      <li class="post">
        <a href="/blog/2017/03/11/2017/">2017技术成长之路</a>
      </li>
    
      <li class="post">
        <a href="/blog/2017/02/17/virtualfunctionandvariadicparametertemplate/">虚函数和变长参数模板的妙用</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/25/singleton/">Singleton与多线程</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/04/introductiontohazardpointer/">Lock Free中的Hazard Pointer(下)</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/03/gccandperfopt/">性能优化的那些传说和迷思</a>
      </li>
    
  </ul>
</section>
<section>
  <h1>Friends' Link</h1>
  <ul>
    <li>
	  <li><a href="http://www.chongh.wiki/">Diting0x</a></li>
	  <li><a href="http://www.xiaolili.net/">wangli</a></li>
	  <li><a href="http://www.skykewei.top">dukewei</a></li>
	  <li><a href="http://irwenqiang.github.io">chenwenqiang</a></li>
      <li><a href="http://www.armsword.com">duruofei</a></li>
    </li>
  </ul>
</section><section>
  <h1>Yebangyu</h1>
  <p>福建人。热爱历史、K歌、NBA</p>
  <p>帝都码农</p>
  <p>历史学家，专治秦汉史</p>
</section>
<section>
 <h1>Categories</h1>
 <ul id="categories">
  <li class='category'><a href='/blog/categories/c-plus-plus/'>c++ (11)</a></li>
<li class='category'><a href='/blog/categories/soupen/'>soupen (4)</a></li>
<li class='category'><a href='/blog/categories/web/'>web (1)</a></li>
<li class='category'><a href='/blog/categories/qi-ta/'>其他 (5)</a></li>
<li class='category'><a href='/blog/categories/li-shi/'>历史 (2)</a></li>
<li class='category'><a href='/blog/categories/bing-xing-bian-cheng/'>并行编程 (20)</a></li>
<li class='category'><a href='/blog/categories/xing-neng-you-hua/'>性能优化 (2)</a></li>
<li class='category'><a href='/blog/categories/suan-fa/'>算法 (4)</a></li>
<li class='category'><a href='/blog/categories/bian-yi-lian-jie/'>编译链接 (2)</a></li>

 </ul>
</section>




  
</aside>


    </div>
  </div>
  <footer role="contentinfo"><!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>
<p>
  Copyright &copy; 2017 - Yebangyu -
  <span class="credit">Powered by <a href="http://octopress.org">Octopress</a></span>
</p>
<script type="text/javascript">var cnzz_protocol = (("https:" == document.location.protocol) ? " https://" : " http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1257548193'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s11.cnzz.com/z_stat.php%3Fid%3D1257548193' type='text/javascript'%3E%3C/script%3E"));</script>

</footer>
  











</body>
</html>
